package org.sunny.sort;

import org.sunny.tools.Integers;
import org.sunny.tools.Times;

/**
 * 冒泡排序
 *  遇到比自己大的元素就进行交换
 *
 * @author Sunny
 * @date 2020/8/15
 */
public class BubbleSort {

    public static void main(String[] args) {
        Integer[] arr1 = Integers.random(1000, 1, 100000);
        Integer[] arr2 = Integers.copy(arr1);
//        Integer[] arr3 = Integers.ascOrder(1, 100000);
        Integer[] arr3 = Integers.tailAscOrder(1, 10000, 2000);

        Times.test("bubbleSort1", () -> bubbleSort1(arr1));
        Times.test("bubbleSort2", () -> bubbleSort2(arr2));
        Times.test("bubbleSort3", () -> bubbleSort3(arr3));
    }

    /**
     * 正常的冒泡排序
     *
     * @param arr 待排序数组
     * @author Sunny
     * @date 2020/8/15
     */
    public static void bubbleSort1(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {
            for (int begin = 1; begin < end; begin++) {
                if (SortUtils.cmp(arr[begin], arr[begin - 1]) < 0) {
                    SortUtils.swap(arr, begin, begin - 1);
                }
            }
        }
    }

    /**
     * 优化1:
     *  考虑在排序过程中已经排序好的情况
     *  优化思路是如果在某次遍历过程中发现没有交换过元素,代表元素已经是排序好了,直接结束
     *
     * @param arr 待排序数组
     * @author Sunny
     * @date 2020/8/15
     */
    public static void bubbleSort2(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {
            boolean sorted = true;
            for (int begin = 1; begin < end; begin++) {
                if (SortUtils.cmp(arr[begin], arr[begin - 1]) < 0) {
                    SortUtils.swap(arr, begin, begin - 1);
                    sorted = false;
                }
            }
            if (sorted) {
                break;
            }
        }
    }

    /**
     * 优化2:
     *  考虑尾部已经存在部分有序元素的情况
     *
     * 优化思路
     *  记录最后一次交换元素的位置,之后的遍历只会遍历到这个索引位置
     *
     * @param arr 待排序数组
     * @author Sunny
     * @date 2020/8/15
     */
    public static void bubbleSort3(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {
            int sortedIndex = 1;
            for (int begin = 1; begin < end; begin++) {
                if (SortUtils.cmp(arr[begin], arr[begin - 1]) < 0) {
                    SortUtils.swap(arr, begin, begin - 1);
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }
}
